1. Field of the Invention
The invention relates to a device for the digital performance of a operation of division adapted to a non-restoring type of method (namely a method with non-restoring of partial remainders). It can be applied more particularly to the computation of the binary division operations of integer or fractional numbers (fixed point). It can be applied especially to digital signal processors.
2. Description of the Prior Art
The computation of binary division operations uses chiefly operations of comparison and subtraction. It should be furthermore take account of a certain number of problems such as the format of the operands (whether fractional or integer), the sign of the result, the unexpected occurrence of null partial results which may lead to an invalid result, etc. In general, a register which shall be called an accumulator is used for the dividend and a source register is used for the divider. The register used for the dividend, namely the accumulator, then contains, for each division step, on the most significant bits, the computed remainder and on the least significant bits, the computed quotient.
To enable the processing, without distinction, of integer or fractional formats whether signed or unsigned, a division approach known as that of non-restoring of partial remainders is used. This approach is based on the sign of the result of subtraction or addition of the partial remainder and of the divider. As its name indicates, it is possible that the partial results may not be accurate: for a given division step, if the quotient bit computed in the previous step is null, then since the divider will have been subtracted all the same, the divider should be added to the partial remainder to recover the correct partial remainder.
For each step of the division, it is necessary to compute the new quotient and the new partial remainder.
Several implementations of the algorithm in a computation device are possible. The invention is concerned particularly with a mode of implementation using the same register containing, at the outset, the dividend to memorize the successive partial remainders and the quotient throughout the division. The remainder is memorized on the most significant bits and the quotient on the least significant bits. This implementation includes the following successive operations for each division step i:
the shifting of the register containing the partial remainder and the quotient by one position leftwards; PA1 the introduction of the reverse of the complemented quotient bit computed at the previous step i-1 on the rightmost position of the register; PA1 the computation of the partial remainder by the addition or subtraction of the divider aligned on the most significant bits of the register, according to the binary value of the complementary quotient bit computed at the step i-1 of the previous division; PA1 the computation of the complemented quotient bit for the next i+1 step, as a function of the sign of the new partial remainder and of the sign of the divider.
This process continues until n shifts have been made, in assuming the divider has a n magnitude bits and that it is desired to obtain a quotient of n magnitude bits.
However, this algorithm entails the assumption that a certain number of conditions are verified so that the final quotient is accurate.
In particular if, during a division step, there is a null partial remainder, the quotient obtained after the last division step may be false. Indeed, a null number is considered to be positive. For a binary division, the sign of the remainder from a division step i is compared with the sign of the divider. It can be seen therefore that, if the divider is negative, the null remainder that is interpreted as being positive is wrongly interpreted, leading to an addition of the divider and not to a subtraction at the next division step. The final quotient is therefore false. It is corrected by adding a 1 to it on the least significant position.
Furthermore, it cannot be certain that a null partial remainder will be detected, for the remainder and the quotient have a variable size: at each division step, the remainder loses one magnitude bit while the quotient gains one. They are therefore operands whose size is variable as a function of the division step. Since they are in the same register, a complex circuitry is needed to follow the progress of the size of the remainder as a function of the division step and to determine the number of bits on which the zero detection has to be done.
Among other conditions, it is also necessary for the dividend to be smaller in terms of absolute value than the divider. If not, the division is not possible. In a signed division, it is also necessary to know whether the divider and the dividend have the same sign or opposite signs, in order to add or not add a unit on the least significant position of the quotient and correct the quotient accordingly when the divider and the dividend have opposite signs.
It is therefore necessary to treat different conditions to obtain the right result. This is achieved by means of so-called exceptional routines given or to be written by the user according to the needs of his application (format, size of the numbers to be processed). Apart from the fact that these routines are costly in terms of time, it is also possible that they do not process every case properly for want of following the division step by step. They are performed beforehand to ascertain that the division is possible or afterwards, to correct the quotient obtained if necessary.
To simplify the implementation of the algorithm, notably the problem of null partial remainders, certain manufacturers of these computation devices have limited the format of the operands at input. For example, certain devices work only on positive operands or only on positive dividers. There is no longer the problem of negative dividers. However, other routines are needed to test the signs and memorize them and to transform the negative operands into positive operands before the computation, and a routine is needed to give the quotient its right sign after the computation.
These manufacturers have also designed one register for the remainder and one register for the quotient to facilitate the detection of the null partial remainder. This approach however complicates the management of these registers for the division.
All these choices of registers, exceptional routines, correct formatting and correction of the quotient increase the number of instruction cycles and hence the computation time. And if it is desired to have a final remainder that is accurate, it is again necessary to carry out processing operations for different conditions to find out if this remainder is accurate and to correct it if necessary.